package main

import "fmt"

type Node struct {
	value int
	left *Node
	right *Node
}
//添加
func (n *Node) add(value int) {
	if value < n.value {
		if n.left == nil {
			n.left = &Node{value: value}
		} else {
			n.left.add(value)
		}
	} else {
		if n.right == nil {
			n.right = &Node{value: value}
		} else {
			n.right.add(value)
		}
	}
}

//先序遍历
//根左右
func PreTravel(root *Node){
	if root != nil{
		fmt.Printf("%d \n", root.value)
		PreTravel(root.left)
		PreTravel(root.right)
	}
}
//中序遍历
//左根右
func MidTravel(root *Node){
	if root != nil{
		MidTravel(root.left)
		fmt.Printf("%d \n", root.value)
		MidTravel(root.right)
	}
}

//后序遍历
//左右根
func PTravel(root *Node){
	if root != nil{
		PTravel(root.left)
		PTravel(root.right)
		fmt.Printf("%d \n", root.value)
	}
}

//找到最近的公共节点
func Nearest(root, p, q *Node) *Node{
	if root == nil || root == p || root == q {
		return root
	}
	l := Nearest(root.left, p ,q)
	r := Nearest(root.right, p, q)
	if l != nil && r != nil{
		return root
	}
	if l != nil{
		return l
	}
	return r
}

func main(){
	root := &Node{value: 30}
	root.add(2)
	root.add(40)
	root.add(20)
	root.add(10)


	PreTravel(root)

	fmt.Println("####################")
	MidTravel(root)

	fmt.Println("####################")
	PTravel(root)

	N_node := Nearest(root, root.right.right, root.left.right)
	fmt.Println(N_node)
}
